#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right; 
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinaryTree {
private:
    Node* root;

    void inOrder(Node* node) {
        if (node == nullptr) return;
        inOrder(node->left);
        cout << node->data << " ";
        inOrder(node->right);
    }

    int getHeightHelper(Node* node) {
        if (node == nullptr) return 0;
        return 1 + max(getHeightHelper(node->left), getHeightHelper(node->right));
    }

public:
    BinaryTree() : root(nullptr) {}

    void insert(int value) {
        if (root == nullptr) {
            root = new Node(value);
            return;
        }
        Node* current = root;
        while (true) {
            if (value < current->data) {
                if (current->left == nullptr) {
                    current->left = new Node(value);
                    break;
                }
                current = current->left;
            } else {
                if (current->right == nullptr) {
                    current->right = new Node(value);
                    break;
                }
                current = current->right;
            }
        }
    }

    bool search(int value) {
        Node* current = root;
        while (current != nullptr) {
            if (value == current->data) return true;
            current = (value < current->data) ? current->left : current->right;
        }
        return false;
    }

    void printInOrder() {
        inOrder(root);
        cout << endl;
    }

    int getHeight() {
        return getHeightHelper(root);
    }
};

int main() {
    BinaryTree tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);
    cout << "Обход в порядке in-order: ";
    tree.printInOrder();
    cout << "Поиск числа 4: " << (tree.search(4) ? "Найдено" : "Не найдено") << endl;
    cout << "Поиск числа 9: " << (tree.search(9) ? "Найдено" : "Не найдено") << endl;
    cout << "Высота дерева: " << tree.getHeight() << endl;

    return 0;
}
